package com.example.common_database;

import java.util.Arrays;

/**
 * Author: liaohailong
 * Date: 2022/2/9
 * Time: 15:07
 * Description:
 **/
public class DPStudy {

    // [2,3,1,1,4]
    // [3,2,1,0,4]
    // 跳跃游戏 从头开始
//    public boolean canJump(int[] nums) {
//        int max = nums[0];
//        for (int i = 1; i < nums.length - 1; i++) {
//            if (i <= max)
//                max = Math.max(max, i + nums[i]);
//        }
//        return max >= nums.length - 1;
//    }

    // 跳跃游戏 从尾开始
    public boolean canJump(int[] nums) {
        int last = nums.length - 1;
        for (int i = nums.length - 2; i >= 0; i--) {
            if (i + nums[i] >= last) {
                last = i;
            }
        }
        return last <= 0;
    }

    // 不同路径
    public int uniquePaths(int m, int n) {
        int[][] matrix = new int[m][n];
        return _uniquePaths(m - 1, n - 1, matrix);
    }

    private int _uniquePaths(int m, int n, int[][] matrix) {
        // ps：枚举出矩阵内的路线数量，发现规律，到达自身点的总路径数量是它左边点和上面点的数量之和
        // dp[y][x] = dp[y][x-1] + dp[y-1][x]
        // if (m < 0 || n < 0) return 0;
        // if (y == 0 || x == 0) return 1;
        if (m < 0 || n < 0) return 0;
        if (m == 0 || n == 0) return 1;
        if (matrix[m][n] != 0) return matrix[m][n];
        int left = _uniquePaths(m, n - 1, matrix);
        matrix[m][n - 1] = left;
        int top = _uniquePaths(m - 1, n, matrix);
        matrix[m - 1][n] = top;
        return left + top;
    }

    // 零钱兑换
    public int coinChange(int[] coins, int amount) {
        // dp[i] i为0到amount金额，值为需要换的最少面值
        // coins[]中的等额面值，dp[coins[j]] = 1，金额命中了coins，就只需要一张
        // amount - coins[j] = x
        // dp[x] = count
        // dp[amount] = count + 1
        // dp[i] = dp[i - coins[j]] + 1

        // dp[amount + 1]，从dp[0]~dp[amount+1]初始化为-1，-1表示无法交换成功

        int[] dp = new int[amount + 1];
        Arrays.fill(dp, -1);
        dp[0] = 0;

        for (int i = 1; i <= amount; i++) {

            for (int j = 0; j < coins.length; j++) {
                //                          dp[i - coins[j]] == -1 表示找不开
                if (coins[j] <= i && dp[i - coins[j]] != -1) {
                    int count = dp[i - coins[j]] + 1;
                    if (dp[i] == -1 || dp[i] > count)
                        dp[i] = count;
                }
            }

        }

        return dp[amount];
    }

    // 最长上升子序列
    public int lengthOfLIS(int[] nums) {
        // 每个下标独立成为一个子序列，那么最坏的情况是长度都为1
        // 定义dp[i]，i表示下标，dp[i]表示该下标最长子序列
        // length-1元素的子序列肯定为1
        // 从length-2开始，往前面推算dp[i]
        // dp[i] = j:num[i] ~ num[length-1] 中 if(num[i]<num[j]) dp[i] = max(dp[i],dp[j]+1)
        // 从尾部开始计算，第i个元素的最长子序列是第i+1个元素最长子序列+1

        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);

        int max = 1;
        for (int i = nums.length - 2; i >= 0; i--) {
            for (int j = i + 1; j <= nums.length - 1; j++) {
                if (nums[i] < nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                    max = Math.max(max, dp[i]);
                }
            }
        }

        return max;
    }

    // 跳跃游戏2
//    public int jump(int[] nums) {
//        int[] dp = new int[nums.length];
//        for (int i = 0; i < nums.length; i++) {
//            dp[i] = nums.length - i - 1;
//        }
//        for (int i = nums.length - 2; i >= 0; i--) {
//            for (int j = nums.length - 1; j > i; j--) {
//                if (i + nums[i] >= j)
//                    dp[i] = Math.min(dp[j] + 1, dp[i]);
//            }
//        }
//
//        return dp[0];
//    }

    // 跳跃游戏2
    public int jump(int[] nums) {
        int length = nums.length;
        int end = 0;
        int maxPosition = 0;
        int steps = 0;
        for (int i = 0; i < length - 1; i++) {
            maxPosition = Math.max(maxPosition, i + nums[i]);
            if (i == end) {
                end = maxPosition;
                steps++;
            }
        }
        return steps;
    }

    // 740. 删除并获得点数
    public int deleteAndEarn(int[] nums) {
        int max = 0;
        for (int num : nums) {
            if (num > max) max = num;
        }

        int[] arr = new int[max + 1];
        for (int num : nums) {
            arr[num] += num;
        }

        return _deleteAndEarn(arr);
    }

    // 打家劫舍
    private int _deleteAndEarn(int[] arr) {
        int[] dp = new int[arr.length];
        dp[0] = arr[0];
        dp[1] = Math.max(arr[0], arr[1]);

        for (int i = 2; i < arr.length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + arr[i]);
        }
        return dp[dp.length - 1];
    }
}
